package dp

import (
	"fmt"
	"math"
	"sort"
)

type item struct {
	Weight int     //重量
	Value  int     //价值
	Rate   float64 // Value/Weight 越大越优先选
}

var Capacity int
var Items []item
var N int //物品数量

// Menu   运行实验三只需调用该函数即可
func Menu() {
	//建议的测试数据
	// 物品个数：4        背包容量：70
	// 物品重量：69 2 2 3
	// 物品价值：70 4 20 30
	var choice int
	fmt.Println("请选择选项：")
	fmt.Println("1.使用贪心求分数背包问题")
	fmt.Println("2.使用贪心求解01背包问题")
	fmt.Println("3.蛮力法求解01背包问题")
	fmt.Println("4.动态规划求解01背包问题")
	fmt.Println("5.动态规划改进法求01背包问题")

	fmt.Scanf("%d", &choice)
	Sscan()
	var weight, value []int
	for i := 0; i < N; i++ {
		weight = append(weight, Items[i].Weight)
		value = append(value, Items[i].Value)
	}
	switch choice {
	case 1:
		res := FractionalKnapsack()
		fmt.Println("使用贪心算法求分数背包问题结果为：", res)
	case 2:
		res := Greedy01Knapsack()
		fmt.Println("使用贪心算法求解01背包问题结果为：", res)
	case 3:
		res := Force01()
		fmt.Println("使用暴力枚举求解01背包问题结果为：", res)
	case 4:
		res := dp01(weight, value, Capacity)
		fmt.Println("使用动态规划求解01背包问题结果为：", res)
	case 5:
		res := dp01Better(weight, value, Capacity)
		fmt.Println("使用改进的动态规划求解01背包问题结果为：", res)
	}
}

func Sscan() {
	fmt.Println("请输入物品数量：")
	_, err := fmt.Scan(&N)
	Items = make([]item, N)
	if err != nil {
		panic("录入失败")
	}
	fmt.Println("请输入背包容量：")
	_, err = fmt.Scan(&Capacity)
	if err != nil {
		panic("录入失败")
	}
	fmt.Println("请依次输入物品的重量：")
	for i := 0; i < N; i++ {
		fmt.Scan(&Items[i].Weight)
	}
	fmt.Println("请依次输入物品的体积：")
	for i := 0; i < N; i++ {
		fmt.Scan(&Items[i].Value)
	}

	//  处理rate
	for i := 0; i < N; i++ {
		Items[i].Rate = float64(Items[i].Value) / float64(Items[i].Weight)
	}
}

// FractionalKnapsack 分数背包问题
func FractionalKnapsack() float64 {
	// 按照比值从大到小排序
	sort.SliceStable(Items, func(i, j int) bool {
		return Items[i].Rate > Items[j].Rate
	})
	cap := Capacity
	p := 0
	ans := float64(0)
	for cap > 0 {
		if Items[p].Weight >= cap { //这个物品的体积大于剩余空间了
			ans += Items[p].Rate * float64(cap)
			cap = 0
		} else {
			ans += float64(Items[p].Value)
			cap = cap - Items[p].Weight
		}
		p++
	}
	return ans
}

// Greedy01Knapsack 贪心求解01背包
func Greedy01Knapsack() int {
	sort.SliceStable(Items, func(i, j int) bool {
		return Items[i].Rate > Items[j].Rate
	})
	p := 0
	ans := 0
	for Capacity > 0 {
		if Items[p].Weight >= Capacity { //这个物品的体积大于剩余空间了
			break
		} else {
			ans += Items[p].Value
			Capacity = Capacity - Items[p].Weight
		}
		p++
	}
	return ans
}

// Force01 暴力法求解01背包问题
func Force01() int {
	return solve(0, Capacity)
}

//从第i个物品开始挑选总重小于j的部分
func solve(i int, j int) int {
	var res int
	if i == len(Items) { //已经没有剩余的物品了
		res = 0
	} else if j < Items[i].Weight {
		res = solve(i+1, j)
	} else {
		res = int(math.Max(float64(solve(i+1, j)), float64(solve(i+1, j-Items[i].Weight)+Items[i].Value))) //一个物品选还是不选都试一下
	}
	return res
}

//  动态规划求解01背包问题
func dp01(weight, value []int, cap int) int {
	dp := make([][]int, 0) //dp[i][j]表示容量j下前i个物品最大的value
	for i := 0; i <= len(value); i++ {
		dp = append(dp, make([]int, cap+1))
	}
	for i := 1; i <= cap; i++ {
		for j := 1; j <= len(weight); j++ {
			curValue := value[j-1]
			curWeight := weight[j-1]
			if i >= curWeight {
				//这个物品可以装或者不装
				yes := dp[j-1][i-curWeight] + curValue
				dp[j][i] = max(dp[j-1][i], yes)
			} else {
				//不装
				dp[j][i] = dp[j-1][i]
			}
		}
	}
	return dp[len(value)][cap]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 滚动数组优化
func dp01Better(weight, value []int, bagWeight int) int {
	// 初始化
	dp := make([]int, bagWeight+1)
	// 递推顺序
	for i := 0; i < len(weight); i++ {
		// 这里必须倒序,区别二维,因为二维dp保存了i的状态
		for j := bagWeight; j >= weight[i]; j-- {
			// 递推公式
			dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
		}
	}
	return dp[bagWeight]
}
